#pragma once

#include<iostream>
#include<vector>
using namespace std;

class Solution
{
public:
     int value(vector<int>& cost,int i,int n)
     {
         if(i >= n) return 0;

         int value1 = cost[i];
         int value2 = cost[i];

         value1 += value(cost,++i,n);
         value2 += value(cost,++i,n);

         return value1 < value2 ? value1 : value2;
     }

     int minCostClimbingStairsRecursion(vector<int>& cost) 
     {
         //int pos = cost[0] < cost[1] ? 0 : 1;
         int value1 = value(cost,0,cost.size());
         int value2 = value(cost,1,cost.size());

         return value1 < value2 ? value1 : value2;
         //return value1;
     }

     int minCostClimbingStairsPrevOrder(vector<int>& cost) 
     {
         int n = cost.size();
         vector<int> ret(n + 1);
         //vector<int> min(cost.size());

         ret.resize(n + 1,0);
         //min.resize(cost.size(),0);
         ret[0] = 0,ret[1] = 0;
         for(int i = 2;i <= n;++i)
         {
             int x = (ret[i - 1] + cost[i - 1]);
             int y = (ret[i - 2] + cost[i - 2]);
             ret[i] = x < y ? x : y;
         }
         return ret.back();
     }

    int minCostClimbingStairsBehindOrder(vector<int>& cost)
    {
        int n = cost.size();
        vector<int> ret(n + 1, 0);

        ret[n] = 0;
        ret[n - 1] = cost[n - 1];
        ret[n - 2] = cost[n - 2];
        for (int i = n - 3; i >= 0; --i)
        {
            ret[i] = min(ret[i + 1] + cost[i], ret[i + 2] + cost[i]);
        }

        return min(ret[0], ret[1]);
    }
};